class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        vector<vector<int>>f(n+1,vector<int>(n+1,1));
        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                f[i][j]=(s[i]==s[j])?f[i+1][j-1]:0;
            }
        }
        //cout<<"x=="<<f[1][3]<<endl;
        int ma=0;
        int idx=0;
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                if(f[i][j]){
                    if(j-i+1>ma){
                        ma=j-i+1;
                        idx=i;
                    }
                }
            }
        }
        cout<<"ma=="<<ma<<endl;
        return s.substr(idx,ma);
    }
};